# Shortest Path

• 2026년 8월 11일 알고리즘
  플로이드·워셜의 메모리 줄이기 — N³칸에서 N²칸으로

  플로이드·워셜은 D[k][i][j]로 N³칸을 쓴다. k를 계산할 때 k-1층만 참조한다는 점에서 2층으로 줄이고, D^{k-1}[i][k]와 D^k[i][k]가 같다는 것을 보여 1층으로 줄인다. 덮어써도 답이 변하지 않는 이유를 증명한다.

• 2026년 8월 11일 알고리즘
  모든 쌍 최단 거리 — 다익스트라 N번과 플로이드·워셜

  한 시작점이 아니라 모든 노드 쌍의 최단 거리를 구한다. 다익스트라를 N번 돌리는 기준선을 세우고, 경유할 수 있는 노드를 {1..k}로 제한해 k를 늘려 가는 플로이드·워셜을 유도한다. 점화식 D^k[i][j]=min(D^{k-1}[i][j], D^{k-1}[i][k]+D^{k-1}[k][j])가 왜 성립하는지 양방향으로 증명한다.

• 2026년 6월 1일 알고리즘
  다익스트라 알고리즘 2 — 최단 경로 복원, 시간 복잡도, 그리고 Prim과의 비교

  다익스트라 알고리즘에서 부모 배열로 최단 경로를 복원하고, 우선순위 큐로 O(m log n)을 달성한 뒤 Prim 알고리즘과 차이를 비교한다.

• 2026년 5월 29일 알고리즘
  다익스트라 알고리즘 1 — 각 정점까지의 최단 거리만 구하기

  다익스트라 알고리즘으로 한 시작점에서 모든 정점까지 최단 거리를 구한다. 확정 집합을 키우며 가장 가까운 정점을 추가하는 그리디 전략을 보고, 왜 최소 d_min이 정답인지·왜 추가한 정점의 간선만 갱신하면 되는지를 증명한다.

• 2026년 5월 18일 알고리즘
  그리디 알고리즘 — 매 순간 가장 좋아 보이는 선택

  그리디 알고리즘은 매 단계에서 가장 좋아 보이는 선택을 하고 그 선택을 번복하지 않는다. selection sort와 최단 경로 문제를 통해 그리디의 작동 원리를 살펴보고, 눈앞의 최적이 전체 최적이 아닐 수 있는 한계를 확인한다.